#include <dbg.h>
#include <gtest/gtest.h>

#include <climits>
using namespace std;

#ifdef SILY
class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int res = INT_MAX;
        int n = nums.size();

        // 前缀最小值
        vector<int> pre(n);
        pre[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            pre[i] = min(pre[i - 1], nums[i]);
        }
        dbg(pre);

        // 后缀最小值
        vector<int> suf(n);
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = min(suf[i + 1], nums[i]);
        }
        dbg(suf);

        // 遍历
        for (int i = 1; i < n - 1; ++i) {
            if (pre[i] < nums[i] && nums[i] > suf[i + 1]) {
                res = min(res, pre[i - 1] + nums[i] + suf[i + 1]);
            }
        }

        return res == INT_MAX ? -1 : res;
    }
};
#else
class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n = nums.size();

        // 后缀最小值
        vector<int> suf(n);
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i > 1; --i) {
            suf[i] = min(suf[i + 1], nums[i]);
        }
        dbg(suf);

        int res = INT_MAX;
        int pre = nums[0];  // 前缀最小值
        for (int j = 1; j < n - 1; ++j) {
            if (pre < nums[j] && nums[j] > suf[j + 1]) {
                res = min(res, pre + nums[j] + suf[j + 1]);
            }
            pre = min(pre, nums[j]);  // 更新前缀最小值
        }
        return res == INT_MAX ? -1 : res;
    }
};
#endif

TEST(MINIMUM_SUM_Test1, minimumSum) {
    Solution s;

    vector<int> nums{8, 6, 1, 5, 3};
    EXPECT_EQ(s.minimumSum(nums), 9);
}

TEST(MINIMUM_SUM_Test2, minimumSum) {
    Solution s;

    vector<int> nums{5, 4, 8, 7, 10, 2};
    EXPECT_EQ(s.minimumSum(nums), 13);
}

TEST(MINIMUM_SUM_Test3, minimumSum) {
    Solution s;

    vector<int> nums{6, 5, 4, 3, 4, 5};
    EXPECT_EQ(s.minimumSum(nums), -1);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}